package com.success.fenbi;

import org.junit.Test;

/**
 * Desc: 2018.12.19
 * 霍庆源粉笔面试题：迷宫
 * 给一个二维数组，数组的值true表示可以走，false表示不可以走，左上角为入口，右下角为出口，如果有路径可以从左上角走到右下角返回true，否则返回false。
 * Create by John Jiang On 2018/12/19
 */
public class Access {

    public boolean pathExist(boolean[][] graph){
        int n = graph.length;
        int m = graph[0].length;
        boolean[][] access = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                access[i][j] = true;
            }
        }
        return search(graph, 0,0, access);
    }

    public boolean search(boolean[][] graph, int i, int j, boolean[][] access) {
        if (i == graph.length - 1 && j == graph[i].length - 1) {
            return graph[i][j];
        }
        access[i][j] = false;
        boolean flag = false;
        // up
        if (i > 0 && access[i - 1][j]) {
            flag = search(graph, i - 1, j, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        // down
        if (i < graph.length - 1 && access[i + 1][j]) {
            flag = search(graph, i + 1, j, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        // left
        if (j > 0 && access[i][j - 1]) {
            flag = search(graph, i, j - 1, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        // right
        if (j < graph[i].length - 1 && access[i][j + 1]) {
            flag = search(graph, i, j + 1, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        access[i][j] = true;
        return false;
    }

    @Test
    public void test() {
        boolean[][] graph = {{true, false, false},{true, false, false}, {true, true, true}};
        System.out.println(pathExist(graph));
    }
}
